#include"TestGraphes.h"
#include"GraphAlgorithms.h"
#include"Generators.h"
#include<set>
#include<Windows.h>
#include<utility>
#include<vector>
#include<stdexcept>
#include<algorithm>
#include<crtdbg.h>
#include<fstream>

void detectedMemoryLeaks(const std::string& testType){
	throw std::runtime_error("Detected memory leaks on " + testType);
}


void unitTestsAdjacent(){
	{
		Graph G;
		int vertexNum = 7;
		int edgesNum = 9;
		std::vector<std::pair<int, int> > edgesList = { { 0, 1 }, { 1, 2 }, { 2, 3 },
		{ 3, 4 }, { 4, 5 }, { 5, 3 }, { 2, 5 }, { 0, 4 }, { 0, 6 } };
		G.readGraph(vertexNum, edgesNum, edgesList);
		std::vector<int> adjacent0 = G.getAdjacentList(0);
		std::sort(adjacent0.begin(), adjacent0.end());
		std::vector<int> correctAnswer0{ 1, 4, 6 };
		if (adjacent0 != correctAnswer0){
			throw std::logic_error("Wrong adjacent list 1");
		}
		std::vector<int> adjacent1 = G.getAdjacentList(1);
		std::sort(adjacent1.begin(), adjacent1.end());
		std::vector<int> correctAnswer1{ 2 };
		if (adjacent1 != correctAnswer1){
			throw std::logic_error("Wrong adjacent list 2");
		}
		std::vector<int> adjacent4 = G.getAdjacentList(4);
		std::sort(adjacent4.begin(), adjacent4.end());
		std::vector<int> correctAnswer4{ 5 };
		if (adjacent4 != correctAnswer4){
			throw std::logic_error("Wrong adjacent list 3");
		}
		std::vector<int> adjacent6 = G.getAdjacentList(6);
		std::sort(adjacent6.begin(), adjacent6.end());
		std::vector<int> correctAnswer6;
		if (adjacent6 != correctAnswer6){
			throw std::logic_error("Wrong adjacent list 3");
		}


	}
}
void memoryCheckEmptyGraph(){

#ifdef _DEBUG
	std::ofstream out(".\\MemoryLogs\\empty.log");
	for (int vertexNum = 0; vertexNum < 100; ++vertexNum){
		_CrtMemState beforeGraph;
		_CrtMemCheckpoint(&beforeGraph);
		{

			_CrtMemState memoryStateBeforeCreating;
			_CrtMemState memoryStateAfterCreating;
			_CrtMemCheckpoint(&memoryStateBeforeCreating);

			std::vector<std::pair<int, int> > edgesList;
			Graph G;
			G.readGraph(100 * vertexNum, 0, edgesList);

			_CrtMemCheckpoint(&memoryStateAfterCreating);
			_CrtMemState differenceMemory;
			_CrtMemDifference(&differenceMemory,
				&memoryStateBeforeCreating, &memoryStateAfterCreating);

			out << "Memory size used by empty graph on "
				<< vertexNum * 100 << " vertexes is " << differenceMemory.lTotalCount << " bytes" << std::endl;

		}

		_CrtMemState afterGraph;
		_CrtMemCheckpoint(&afterGraph);
		_CrtMemState differenceMemory;
		if (_CrtMemDifference(&differenceMemory, &beforeGraph, &afterGraph)){
			detectedMemoryLeaks("empty graph");
		}
	}
	out.close();
#endif
}

void timeCheckEmptyGraphs(){
#ifndef _DEBUG
	std::ofstream out(".\\TimeLogs\\empty.log");
	for (int vertexNum = 0; vertexNum < 100; ++vertexNum){
		{

			std::vector<std::pair<int, int> > edgesList;
			Graph G;
			G.readGraph(100 * vertexNum, 0, edgesList);

			DefaultUserClass defClass;
			int time1 = GetTickCount();
			DFS(G, &defClass);
			int time2 = GetTickCount();
			out << "Time used by DFS on empty graph on " << 100 * vertexNum <<
				" vertexes is " << (time2 - time1) << " ms" << std::endl;

		}
	}
	out.close();
#endif
}


void memoryCheckFullGraph(){
#ifdef _DEBUG
	std::ofstream out(".\\MemoryLogs\\full.log");
	for (int vertexNum = 0; vertexNum < 200; ++vertexNum){
		_CrtMemState beforeGraph;
		_CrtMemCheckpoint(&beforeGraph);
		{
			_CrtMemState memoryStateBeforeCreating;
			_CrtMemState memoryStateAfterCreating;
			std::vector<std::pair<int, int> > edgesList;
			for (int fromVertex = 0; fromVertex < vertexNum; ++fromVertex){
				for (int toVertex = fromVertex + 1; toVertex < vertexNum; ++toVertex){
					edgesList.push_back({ fromVertex, toVertex });
					edgesList.push_back({ toVertex, fromVertex });
				}
			}

			_CrtMemCheckpoint(&memoryStateBeforeCreating);
			Graph G;
			G.readGraph(vertexNum, vertexNum*(vertexNum - 1), edgesList);
			_CrtMemCheckpoint(&memoryStateAfterCreating);
			_CrtMemState differenceMemory;
			_CrtMemDifference(&differenceMemory,
				&memoryStateBeforeCreating, &memoryStateAfterCreating);
			out << "Memory size used by full graph on "
				<< vertexNum << " vertexes is " << differenceMemory.lTotalCount << " bytes" << std::endl;
		}
		_CrtMemState afterGraph;
		_CrtMemCheckpoint(&afterGraph);
		_CrtMemState differenceMemory;
		if (_CrtMemDifference(&differenceMemory, &beforeGraph, &afterGraph)){
			detectedMemoryLeaks("full graph");
		}
	}
	out.close();
#endif
}

void timeCheckFullGraph(){
#ifndef _DEBUG
	std::ofstream out(".\\TimeLogs\\full.log");
	for (int vertexNum = 0; vertexNum < 200; ++vertexNum){
		{
			std::vector<std::pair<int, int> > edgesList;
			for (int fromVertex = 0; fromVertex < vertexNum; ++fromVertex){
				for (int toVertex = fromVertex + 1; toVertex < vertexNum; ++toVertex){
					edgesList.push_back({ fromVertex, toVertex });
					edgesList.push_back({ toVertex, fromVertex });
				}
			}
			Graph G;
			G.readGraph(vertexNum, vertexNum*(vertexNum - 1), edgesList);
			DefaultUserClass defClass;
			int time1 = GetTickCount();
			DFS(G, &defClass);
			int time2 = GetTickCount();

			out << "Time used by DFS on full graph on " << vertexNum <<
				" vertexes is " << (time2 - time1) << " ms" << std::endl;
		}

	}
	out.close();
#endif
}

void memoryCheckRandomGraph(){
#ifdef _DEBUG
	std::ofstream out(".\\MemoryLogs\\random.log");
	for (int testCount = 0; testCount < 50; ++testCount){
		int vertexNum = getRandomPositiveNumber() % 10000;
		int edgesNum = min(getRandomPositiveNumber() % 100000, vertexNum * 10);
		//int edgesNum = vertexNum * 10;

		_CrtMemState beforeGraph;
		_CrtMemCheckpoint(&beforeGraph);

		{

			_CrtMemState memoryStateBeforeCreating;
			_CrtMemState memoryStateAfterCreating;

			std::vector<std::pair<int, int> > edgesList;
			for (int edgesCount = 0; edgesCount < edgesNum; ++edgesCount){
				edgesList.push_back(getRandomEdge(vertexNum));
			}
			_CrtMemCheckpoint(&memoryStateBeforeCreating);
			Graph G;
			G.readGraph(vertexNum, edgesNum, edgesList);
			_CrtMemCheckpoint(&memoryStateAfterCreating);
			_CrtMemState differenceMemory;
			_CrtMemDifference(&differenceMemory,
				&memoryStateBeforeCreating, &memoryStateAfterCreating);
			out << "Memory size used by random graph on "
				<< vertexNum << " vertexes and " << edgesNum << "egdes is " << differenceMemory.lTotalCount << " bytes" << std::endl;

		}

		_CrtMemState afterGraph;
		_CrtMemCheckpoint(&afterGraph);
		_CrtMemState differenceMemory;
		if (_CrtMemDifference(&differenceMemory, &beforeGraph, &afterGraph)){
			detectedMemoryLeaks("random graph");
		}
	}
	out.close();

#endif
}

void timeCheckRandomGraph(){
#ifndef _DEBUG
	std::ofstream out(".\\TimeLogs\\random.log");
	for (int testCount = 0; testCount < 50; ++testCount){
		int vertexNum = getRandomPositiveNumber() % 10000;
		int edgesNum = min(getRandomPositiveNumber() % 100000, vertexNum * 10);
		//int edgesNum = vertexNum * 10;

		{

			std::vector<std::pair<int, int> > edgesList;
			for (int edgesCount = 0; edgesCount < edgesNum; ++edgesCount){
				edgesList.push_back(getRandomEdge(vertexNum));
			}
			Graph G;
			G.readGraph(vertexNum, edgesNum, edgesList);
			DefaultUserClass defClass;
			int time1 = GetTickCount();
			DFS(G, &defClass);
			int time2 = GetTickCount();
			out << "Time used by DFS on random graph on " << vertexNum <<
				" vertexes and " << edgesNum << " edges is " << (time2 - time1) << " ms" << std::endl;

		}
	}
	out.close();
#endif
}

void checkTopologySort(Graph& G, const std::vector<int>& answerOrder){
	int vertexNum = G.getVertexNum();
	std::set<std::pair<int, int> > badEdgesSet;
	for (int fromVertex = 0; fromVertex < vertexNum; ++fromVertex){
		std::vector<int> adjacentList = G.getAdjacentList(fromVertex);
		for (auto toVertex : adjacentList){
			badEdgesSet.insert({ toVertex, fromVertex });
		}
	}
	for (size_t mayFromVertex = 0; mayFromVertex < answerOrder.size(); ++mayFromVertex){
		for (size_t mayToVertex = mayFromVertex + 1; mayToVertex < answerOrder.size(); ++mayToVertex){
			if (badEdgesSet.count({ answerOrder[mayFromVertex], answerOrder[mayToVertex] }) > 0){
				throw std::logic_error("Wrong topology sort order");
			}
		}
	}
}

void timeAndTopologyCheckAcyclicGraph(){
#ifndef _DEBUG
	std::ofstream out(".\\TimeLogs\\acyclic.log");
	for (int testCount = 0; testCount < 100; ++testCount){
		int vertexNum = max(10, getRandomPositiveNumber() % 1000);
		int edgesNum = min(getRandomPositiveNumber() % 10000, vertexNum * 10);
		{
			std::vector<int> orderVertex(vertexNum);
			for (int counter = 0; counter < vertexNum; ++counter){
				orderVertex[counter] = counter;
			}
			std::random_shuffle(orderVertex.begin(), orderVertex.end());
			std::vector<std::pair<int, int> > edgesList;
			for (int edgesCount = 0; edgesCount < edgesNum; ++edgesCount){
				std::pair<int, int> indexEdge = getRandomIndexes(vertexNum);
				edgesList.push_back({ orderVertex[indexEdge.first], orderVertex[indexEdge.second] });
			}
			Graph G;
			G.readGraph(vertexNum, edgesNum, edgesList);
			DefaultUserClass defClass;
			int time1 = GetTickCount();
			DFS(G, &defClass);
			int time2 = GetTickCount();
			out << "Time used by DFS on acyclic graph on " << vertexNum <<
				" vertexes and " << edgesNum << " edges is " << (time2 - time1) << " ms" << std::endl;

			topologySortClass topologyHandler;
			DFS(G, &topologyHandler);


			std::vector<int> sortResult = topologyHandler.getTopologyOrder();
			checkTopologySort(G, sortResult);
		}
	}
	out.close();
#endif
}

void memoryCheckAcyclicGraph(){
#ifdef _DEBUG
	std::ofstream out(".\\MemoryLogs\\acyclic.log");
	for (int testCount = 0; testCount < 100; ++testCount){
		int vertexNum = max(10, getRandomPositiveNumber() % 1000);
		int edgesNum = min(getRandomPositiveNumber() % 10000, vertexNum * 10);
		//int edgesNum = vertexNum * 10;
		_CrtMemState beforeGraph;
		_CrtMemCheckpoint(&beforeGraph);
		{
			_CrtMemState memoryStateBeforeCreating;
			_CrtMemState memoryStateAfterCreating;
			std::vector<int> orderVertex(vertexNum);
			for (int counter = 0; counter < vertexNum; ++counter){
				orderVertex[counter] = counter;
			}
			std::random_shuffle(orderVertex.begin(), orderVertex.end());
			std::vector<std::pair<int, int> > edgesList;
			for (int edgesCount = 0; edgesCount < edgesNum; ++edgesCount){
				std::pair<int, int> indexEdge = getRandomIndexes(vertexNum);
				edgesList.push_back({ orderVertex[indexEdge.first], orderVertex[indexEdge.second] });
			}
			_CrtMemCheckpoint(&memoryStateBeforeCreating);
			Graph G;
			G.readGraph(vertexNum, edgesNum, edgesList);
			_CrtMemCheckpoint(&memoryStateAfterCreating);
			_CrtMemState differenceMemory;
			_CrtMemDifference(&differenceMemory,
				&memoryStateBeforeCreating, &memoryStateAfterCreating);
			out << "Memory size used by acyclic graph on "
				<< vertexNum << " vertexes and " << edgesNum << " egdes is " << differenceMemory.lTotalCount << " bytes" << std::endl;
		}
		_CrtMemState afterGraph;
		_CrtMemCheckpoint(&afterGraph);
		_CrtMemState differenceMemory;
		if (_CrtMemDifference(&differenceMemory, &beforeGraph, &afterGraph)){
			detectedMemoryLeaks("acyclic graph");
		}
	}
	out.close();
#endif
}

void memoryCheckFunctionalGraphs(){
#ifdef _DEBUG
	std::ofstream out(".\\MemoryLogs\\functional.log");
	for (int testCount = 0; testCount < 100; ++testCount){
		int vertexNum = getRandomPositiveNumber() % 10000;
		int edgesNum = vertexNum;
		//int edgesNum = vertexNum * 10;
		_CrtMemState beforeGraph;
		_CrtMemCheckpoint(&beforeGraph);
		{
			_CrtMemState memoryStateBeforeCreating;
			_CrtMemState memoryStateAfterCreating;

			std::vector<std::pair<int, int> > edgesList;
			for (int edgesCount = 0; edgesCount < edgesNum; ++edgesCount){
				edgesList.push_back({ edgesCount, getRandomPositiveNumber() % vertexNum });
			}
			_CrtMemCheckpoint(&memoryStateBeforeCreating);
			Graph G;
			G.readGraph(vertexNum, edgesNum, edgesList);

			_CrtMemCheckpoint(&memoryStateAfterCreating);
			_CrtMemState differenceMemory;
			_CrtMemDifference(&differenceMemory,
				&memoryStateBeforeCreating, &memoryStateAfterCreating);
			out << "Memory size used by functional graph on "
				<< vertexNum << " vertexes is " << differenceMemory.lTotalCount << " bytes" << std::endl;
		}
		_CrtMemState afterGraph;
		_CrtMemCheckpoint(&afterGraph);
		_CrtMemState differenceMemory;
		if (_CrtMemDifference(&differenceMemory, &beforeGraph, &afterGraph)){
			detectedMemoryLeaks("functional graph");
		}
	}
	out.close();
#endif
}

void timeCheckFunctionalGraphs(){
#ifndef _DEBUG
	std::ofstream out(".\\TimeLogs\\functional.log");
	for (int testCount = 0; testCount < 100; ++testCount){
		int vertexNum = getRandomPositiveNumber() % 10000;
		int edgesNum = vertexNum;
		//int edgesNum = vertexNum * 10;
		{

			std::vector<std::pair<int, int> > edgesList;
			for (int edgesCount = 0; edgesCount < edgesNum; ++edgesCount){
				edgesList.push_back({ edgesCount, getRandomPositiveNumber() % vertexNum });
			}
			Graph G;
			G.readGraph(vertexNum, edgesNum, edgesList);

			DefaultUserClass defClass;
			int time1 = GetTickCount();
			DFS(G, &defClass);
			int time2 = GetTickCount();

			out << "Time used by DFS on functional graph on " << vertexNum <<
				" vertexes is " << (time2 - time1) << " ms" << std::endl;
		}
	}
	out.close();
#endif
}

void unitTestsTopology(){
	{
		Graph G;
		int vertexNum = 3;
		int edgesNum = 3;
		std::vector<std::pair<int, int> > edgesList = { { 2, 1 }, { 1, 0 }, { 2, 0 } };
		G.readGraph(vertexNum, edgesNum, edgesList);
		topologySortClass DAG;
		DFS(G, &DAG);
		std::vector<int> sortResult = DAG.getTopologyOrder();
		std::vector<int> correctAnswer{ 2, 1, 0 };
		if (sortResult != correctAnswer){
			throw std::logic_error("Wrong answer on topology sort Unit test 1");
		}
	}
	{
		Graph G;
		int vertexNum = 1;
		int edgesNum = 0;
		std::vector<std::pair<int, int> > edgesList;
		G.readGraph(vertexNum, edgesNum, edgesList);
		topologySortClass DAG;
		DFS(G, &DAG);
		std::vector<int> sortResult = DAG.getTopologyOrder();
		std::vector<int> correctAnswer{ 0 };
		if (sortResult != correctAnswer){
			throw std::logic_error("Wrong answer on topology sort Unit test 2");
		}
	}
	{
		Graph G;
		int vertexNum = 8;
		int edgesNum = 10;
		std::vector<std::pair<int, int> > edgesList = { { 0, 1 }, { 0, 2 },
		{ 0, 3 }, { 1, 4 }, { 2, 4 }, { 3, 4 }, { 4, 5 }, { 4, 6 }, { 5, 7 }, { 6, 7 } };
		G.readGraph(vertexNum, edgesNum, edgesList);
		topologySortClass DAG;
		DFS(G, &DAG);
		std::vector<int> sortResult = DAG.getTopologyOrder();
		std::sort(sortResult.begin() + 1, sortResult.begin() + 4);
		std::sort(sortResult.begin() + 5, sortResult.begin() + 7);
		std::vector<int> correctResult{ 0, 1, 2, 3, 4, 5, 6, 7 };
		if (sortResult != correctResult){
			throw std::logic_error("Wrong answer on topology sort Unit test 3");
		}
	}
}

void BFSUnitTests(){
	{
		Graph G;
		int vertexNum = 3;
		int edgesNum = 3;
		std::vector<std::pair<int, int> > edgesList = { { 2, 1 }, { 1, 0 }, { 2, 0 } };
		G.readGraph(vertexNum, edgesNum, edgesList);
		SimpleBFSClass BFSOrder;
		BFS(G, &BFSOrder);
		std::vector<int> BFSResult = BFSOrder.getBFSOrder();
		std::vector<int> correctAnswer{ 0,1,2 };
		if (BFSResult != correctAnswer){
			throw std::logic_error("Wrong answer BFS Unit test 1");
		}
	}
	{
		Graph G;
		int vertexNum = 1;
		int edgesNum = 0;
		std::vector<std::pair<int, int> > edgesList;
		G.readGraph(vertexNum, edgesNum, edgesList);
		SimpleBFSClass BFSOrder;
		BFS(G, &BFSOrder);
		std::vector<int> BFSResult = BFSOrder.getBFSOrder();
		std::vector<int> correctAnswer{ 0 };
		if (BFSResult != correctAnswer){
			throw std::logic_error("Wrong answer on BFS Unit test 2");
		}
	}
	{
		Graph G;
		int vertexNum = 12;
		int edgesNum = 13;
		std::vector<std::pair<int, int> > edgesList = { { 0, 1 }, { 0, 2 },
		{ 0, 3 }, { 1, 4 }, { 2, 4 }, { 3, 4 }, { 4, 5 }, { 4, 6 }, { 5, 7 }, { 6, 7 }, { 3, 8 }, { 9, 11 }, { 10, 11 } };
		G.readGraph(vertexNum, edgesNum, edgesList);
		std::vector<int> l0 = G.getAdjacentList(0);
		SimpleBFSClass BFSOrder;
		BFS(G, &BFSOrder);
		std::vector<int> BFSResult = BFSOrder.getBFSOrder();
		std::vector<int> correctAnswer{ 0,1,2,3,4,8,5,6,7,9,11,10 };
		if (BFSResult != correctAnswer){
			throw std::logic_error("Wrong answer on BFS Unit test 3");
		}
	}
}


